package org.jiangpeng.learn.linkelist;

import java.util.Collection;
import java.util.Iterator;

/**
 * 自定义单链表
 * 
 * @author jp137
 *
 */
public class SingleLinkeList<E> implements Collection<E> {

	private Node dummyHead;

	private int size;

	public SingleLinkeList() {
		dummyHead = new Node();
		size = 0;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public boolean contains(Object o) {
		Node item = getNode(o);
		if(item.element != null)
			return true;
		return false;
	}

	@Override
	public Iterator<E> iterator() {
		// TODO 待完善
		return null;
	}

	@Override
	public Object[] toArray() {
		Object[] items = new Object[size];
		Node item = dummyHead.next;
		int i = 0;
		while(item.element != null) {
			items[i] = item.element;
			item = item.next;
		}
		return items;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		return a;
	}

	@Override
	public boolean add(E e) {
		return addLast(e);
	}

	public boolean addLast(E e) {
		return add(size, e);
	}

	public boolean add(int index, E e) {
		if (index < 0 || index > size) {
			throw new RuntimeException("index is error!");
		}
		Node prev = getNode(index);
		prev.next = new Node(e, prev.next);
		size++;
		return true;
	}

	private Node getNode(int index) {
		Node node = dummyHead;
		for (int i = 0; i < index; i++)
			node = node.next;
		return node;
	}

	public E get(int index) {
		return getNode(index).element;

	}

	public boolean addFirst(E e) {
		return add(0, e);
	}

	private Node getNode(Object o) {
		if(isEmpty())
			return dummyHead;
		Node item = dummyHead.next;
		while(item.element != null) {
			if(item.element.equals(o))
				return item;
			item = item.next;
		}
		return dummyHead;
	}
	
	@Override
	public boolean remove(Object o) {
		Node removeItem = getNode(o);
		if(removeItem.element == null)
			return false;
		removeItem.element = null;
		removeItem = removeItem.next;
		size--;
		return true;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for(Object e: c)
			if(!contains(e))
				return false;
		return true;
	}

	@Override
	public boolean addAll(Collection<? extends E> c) {
		Node tempNode = getNode(size);
		if(c.isEmpty())
			return false;
		for(E e : c) {
			tempNode = tempNode.next = new Node(e, null);
			size++;
		}
		return true;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		Node temp = null;
		for(Object e:c) {
			temp = getNode(e);
			if(temp.element != null) {
				temp.element = null;
				temp = temp.next;
			}
		}
			
		return true;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		// TODO 待完善
		return false;
	}

	@Override
	public void clear() {
		dummyHead = new Node(null);
		size = 0;

	}

	@Override
	public String toString() {
		StringBuffer builder = new StringBuffer();
		Node cur = dummyHead.next;
		while(cur != null) {
			builder.append(cur.element.toString()).append("->");
			cur = cur.next;
		}
		return builder.append("NULL").toString();
	}
	
	private class Node {
		E element;
		Node next;

		public Node(E element, Node next) {
			this.element = element;
			this.next = next;
		}

		public Node(E element) {
			this(element, null);
		}

		public Node() {
			this(null);
		}

		@Override
		public String toString() {
			return element.toString();
		}
	}
}
